package com.mlick.a.huweiod;

import java.util.HashMap;
import java.util.Scanner;

/**
 * <a href="https://fcqian.blog.csdn.net/article/details/128062246">...</a>
 * 获得 完美走位
 * 题目描述
 * 在第一人称射击游戏中，玩家通过键盘的 A、S、D、W 四个按键控制游戏人物分别向左、向后、向右、向前进行移动，从而完成走位。
 * 假设玩家每按动一次键盘，游戏人物会向某个方向移动一步，如果玩家在操作一定次数的键盘并且各个方向的步数相同时，此时游戏人物必定会回到原点，则称此次走位为完美走位。
 * 现给定玩家的走位（例如：ASDA）,请通过更换其中 一段连续走位的方式使得原走位能够变成一个完美走位。
 * 其中待更换的连续走位可以是相同长度的任何走位。请返回待更换的连续走位的最小可能长度。
 * 若果原走位本身是一个完美走位，则返回 0。
 * 输入描述
 * 输入为由键盘字母表示的走位s，例如：ASDA
 * <p>
 * 输出描述
 * 输出为待更换的连续走位的最小可能长度。
 * <p>
 * 用例
 * 输入	WASDAASD
 * 输出	1
 * 说明	将第二个A替换为W，即可得到完美走位
 * 输入	AAAA
 * 输出	3
 * 说明	将其中三个连续的A替换为WSD，即可得到完美走位
 */
public class H3 {

    /**
     * 解题思路：
     * 最小覆盖子串 <a href="https://blog.csdn.net/qfc_128220/article/details/128092566?spm=1001.2014.3001.5501">...</a>
     * 可以参考 leetcode <a href="https://leetcode.cn/problems/minimum-window-substring/">...</a>
     * <p>
     * 题目要求，保持W,A,S,D字母个数平衡，即相等，如果不相等，可以从字符串中选取一段连续子串替换，来让字符串平衡。
     * <p>
     * 比如：WWWWAAAASSSS
     * <p>
     * 字符串长度12，W,A,S,D平衡的话，则每个字母个数应该是3个，而现在W,A,S各有4个，也就是说各超了1个。
     * <p>
     * 因此我们应该从字符串中，选取一段包含1个W，1个A，1个S的子串，来替换为D。
     * <p>
     * WWWWAAAASSSS
     * <p>
     * WWWWAAAASSSS
     * <p>
     * WWWWAAAASSSS
     * <p>
     * ........
     * <p>
     * WWWWAAAASSSS
     * <p>
     * 而符合这种要求的子串可能很多，我们需要找出其中最短的，即WAAAAS。
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println(getResult(sc.next()));
    }

    public static int getResult(String str) {
        // count用于记录W,A,S,D字母的数量
        HashMap<Character, Integer> count = new HashMap<>();

        for (int i = 0; i < str.length(); i++) {
            Character c = str.charAt(i);
            count.put(c, count.getOrDefault(c, 0) + 1);
        }

        // 平衡状态时，W,A,S,D应该都是avg数量
        int avg = str.length() / 4;

        // total用于记录多余字母个数
        int total = 0;

        // flag表示当前是否为平衡状态，默认是
        boolean flag = true;

        for (Character c : count.keySet()) {
            if (count.get(c) > avg) {
                // 如果有一个字母数量超标，则平衡打破
                flag = false;
                // 此时count记录每个字母超过avg的数量
                count.put(c, count.get(c) - avg);
                total += count.get(c);
            } else {
                count.put(c, 0); // 此时count统计的其实是多余字母，如果没有超过avg,则母表示没有多余字
            }
        }

        // 如果平衡，则输出0
        if (flag) return 0;

        int i = 0;
        int j = 0;
        int minLen = str.length() + 1;

        while (j < str.length()) {
            Character jc = str.charAt(j);

            if (count.get(jc) > 0) {
                total--;
            }
            count.put(jc, count.get(jc) - 1);

            while (total == 0) {
                minLen = Math.min(minLen, j - i + 1);

                Character ic = str.charAt(i);
                if (count.get(ic) >= 0) {
                    total++;
                }
                count.put(ic, count.get(ic) + 1);

                i++;
            }
            j++;
        }
        return minLen;
    }

}
